Since the traditional K-means algorithm can hardly predefine the number of clusters, and performs sensitively to the initial clustering centers and outliers, which may result in unstable and inaccurate results, an improved density-based K-means algorithm was proposed. Firstly, high-density trajectory data points were selected as the initial clustering centers to perform K-means clustering by considering the density of the trajectory data distribution and increasing the weight of the density of important points. Secondly, the clustering results were evaluated by the Between-Within Proportion (BWP) index of cluster validity function. Finally, the optimal number of clusters and clustering were determined according to the clustering results evaluation. Theoretical researches and experimental results show that the improved algorithm can be better at extracting the trajectory key points and keeping the key path information. The accuracy of clustering results was 28 percentage points higher than that of the traditional K-means algorithm and 17 percentage points higher than that of the Density-Based Spatial Clustering of Applications with Noise (DBSCAN) algorithm. The proposed algorithm has a better stability and a higher accuracy in trajectory data clustering.